/*
题目描述：股票的最大利润
股票价格顺序排放在数组中，如何买卖获得利润最大
方法：
最大利润就是所有数对中的最大差值
动态规划
 */
public class E63 {
    public static void main(String[] args) {
        int[] prices = {9,11,8,5,7,12,16,14};
        int res = maxProfit(prices, prices.length);
        System.out.println(res);
    }

    public static int maxProfit(int[] prices, int n) {
        if(prices == null || n < 2){
            return 0;
        }
        int[] preProfit = new int[n];
        int[] postProfit = new int[n];
        //i 天之前买卖的收益
        int minBuy = prices[0];
        for(int i = 1; i < n; i++){
            minBuy = Math.min(prices[i], minBuy);
            preProfit[i] = Math.max(preProfit[i-1], prices[i] - minBuy);
        }
        //i 天之后买卖的收益
        int maxSell = prices[n-1];
        for(int j = n - 2; j >= 0; j--){
            maxSell = Math.max(prices[j], maxSell);
            postProfit[j] = Math.max(postProfit[j+1], maxSell - prices[j]);//!!!!
        }

        int maxProfit = 0;
        for(int i = 0; i < n; i++){
            maxProfit = Math.max(maxProfit, preProfit[i] + postProfit[i]);
        }
        return maxProfit;
    }
}
